#include <stack>
#include <vector>
#include <utility>
#include <iostream>

using namespace std;

namespace AlgoLib
{
	struct TreeNode;
	typedef TreeNode *Link;
	typedef TreeNode *const Const_Link;

	struct TreeNode
	{
		int key;
		Link par;
		Link leftSon;
		Link rightSon;

		TreeNode()
		{
			key = 0;
			par = NULL;
			leftSon = NULL;
			rightSon = NULL;
		}

		~TreeNode()
		{
			if (leftSon != NULL)
			{
				delete leftSon;
			}
			if (rightSon != NULL)
			{
				delete rightSon;
			}
		}
	};

	class SplayTree
	{
	private:
		Link root;
		//void init();
		Link g(const Link) const;
		void rotate(Link, const int = 0);
		Link splay(Link);
		void accessItem(const int);
		Link join(Link, Link);
		//pair < Link, Link > split(const int, Link);
		void insertItem(const int);
		void deleteItem(const int);
		void private_debug(const Link);

	public:
		SplayTree();
		~SplayTree();
		bool inTree(const int x)
		{
			if (root == NULL)
			{
				return false;
			}
			accessItem(x);
			return (root->key == x);
		}

		void insert(const int x)
		{
			insertItem(x);
		}

		void erase(const int x)
		{
			deleteItem(x);
		}

		void debug();
	};

	SplayTree::SplayTree()
	{
		root = NULL;
	}

	SplayTree::~SplayTree()
	{
	}

	inline Link SplayTree::g(const Link x) const
	{
		if (x == NULL || x->par == NULL)
		{
			return NULL;
		}
		return x->par->par;
	}

	void SplayTree::rotate(Link y, const int dir)
	{
		// if dir == 0 then rotateLeft
		// if dir == 1 then rotateRight
		Link x = y->rightSon, z = y->par;
		if (dir != 0)
		{
			x = y->leftSon;
		}
		if (z != NULL)
		{
			if (z->leftSon == y)
			{
				z->leftSon = x;
			}
			else
			{
				z->rightSon = x;
			}
		}
		if (dir == 0)
		{
			y->rightSon = x->leftSon;
			x->leftSon = y;
			if (y->rightSon != NULL)
			{
				y->rightSon->par = y;
			}
		}
		else
		{
			y->leftSon = x->rightSon;
			x->rightSon = y;
			if (y->leftSon != NULL)
			{
				y->leftSon->par = y;
			}
		}
		x->par = z;
		y->par = x;
	}

	Link SplayTree::splay(Link x)
	{
		while (x->par != NULL)
		{
			Link gpar = g(x);
			if (x == x->par->leftSon)
			{
				if (gpar == NULL)
				{
					rotate(x->par, 1);
				}
				else if (x->par == gpar->leftSon)
				{
					rotate(gpar, 1);
					rotate(x->par, 1);
				}
				else
				{ // x->par == gpar->rightSon
					rotate(x->par, 1);
					rotate(x->par, 0);
				}
			}
			else
			{ // x == x->par->rightSon
				if (gpar == NULL)
				{
					rotate(x->par, 0);
				}
				else if (x->par == gpar->rightSon)
				{
					rotate(gpar, 0);
					rotate(x->par, 0);
				}
				else
				{ // x->par == gpar->leftSon
					rotate(x->par, 0);
					rotate(x->par, 1);
				}
			}
		}
		return x;
	}
	
	void SplayTree::accessItem(const int i)
	{
		Link last(root);
		if (root == NULL)
		{
			return;
		}
		while (last->key != i)
		{
			if (last->key > i)
			{
				if (last->leftSon != NULL)
				{
					last = last->leftSon;
				}
				else
				{
					break;
				}
			}
			else
			{
				if (last->rightSon != NULL)
				{
					last = last->rightSon;
				}
				else
				{
					break;
				}
			}
		}
		root = splay(last);
	}

	Link SplayTree::join(Link t1, Link t2){
		if (t1 == NULL)
		{
			return t2;
		}
		Link last(t1);
		while (last->rightSon != NULL)
		{
			last = last->rightSon;
		}
		splay(last);
		if (t2 != NULL)
		{
			t2->par = last;
		}
		last->rightSon = t2;
		return last;
	}

	//pair < Link, Link > SplayTree::split(const int i, Link)
	//{
		/* left tree will contain  *
		 * elements with the key   *
		 * not greater than i,     *
		 * right tree will contain *
		 * other elements          */
	/*	Link NewRoot = accessItem(i, root);
		Link tree1, tree2;
		if (NewRoot->key <= i)
		{
			tree2 = NewRoot->rightSon;
			NewRoot->rightSon = 0;
			tree1 = NewRoot;
		}
		else
		{
			tree1 = NewRoot->leftSon;
			NewRoot->leftSon = 0;
			tree2 = NewRoot;
		}
		return make_pair(tree1, tree2);
	}*/

	void SplayTree::insertItem(const int i)
	{
		Link last(root), prev(root);
		while (last != NULL && last->key != i)
		{
			prev = last;
			if (last->key < i)
			{
				last = last->rightSon;
			}
			else
			{
				last = last->leftSon;
			}
		}
		if (last == NULL)
		{
			last = new TreeNode();
			last->par = prev;
			last->key = i;
			if (prev != NULL)
			{
				if (prev->key < i)
				{
					prev->rightSon = last;
				}
				else
				{
					prev->leftSon = last;
				}
			}
		}
		root = splay(last);
	}

	void SplayTree::deleteItem(const int i)
	{
		accessItem(i);
		Link NewRoot = root;
		if (NewRoot != NULL && NewRoot->key == i)
		{
			Link leftSon = NewRoot->leftSon,
				 rightSon = NewRoot->rightSon;
			if (NewRoot->leftSon != NULL)
			{
				NewRoot->leftSon->par = NULL;
				NewRoot->leftSon = NULL;
			}
			if (NewRoot->rightSon != NULL)
			{
				NewRoot->rightSon->par = NULL;
				NewRoot->rightSon = NULL;
			}
			delete NewRoot;
			root = join(leftSon, rightSon);
		}
		else
		{
			root = NewRoot;
		}
	}

	void SplayTree::private_debug(const Link x)
	{
		if (x != NULL)
		{
			private_debug(x->leftSon);
			cerr << x->key << endl;
			private_debug(x->rightSon);
		}
	}

	void SplayTree::debug()
	{
		if (root == NULL)
		{
			cerr << "empty tree" << endl;
		}
		else
		{
			private_debug(root);
		}
		cerr << endl;
	}
}
